package org.example.myleet.p842;

import java.util.LinkedList;
import java.util.List;

public class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> result = new LinkedList<>();
        dfs(S, 0, result);
        return result;
    }

    /**
     * DFS深度优先搜索答案
     * @param S 字符串
     * @param index 当前探索的位置
     * @param result 结果存储指针
     * @return false-这条路行不通，true-继续向前探索或搜索到底是成功的
     */
    private boolean dfs(String S, int index, List<Integer> result) {
        if (index == S.length()) {
            return result.size() > 2;
        }
        for (int i=index+1; i<=S.length(); i++) {
            String nextNumStr = S.substring(index, i);
            if ((nextNumStr.length() > 1 && nextNumStr.charAt(0) == '0') || nextNumStr.length() > 10 || Long.parseLong(nextNumStr) > Integer.MAX_VALUE) {
                //0X这种淘汰；数字长度大于10淘汰；数字转换后大于Integer最大值的淘汰
                break;
            }
            int nextNum = Integer.parseInt(nextNumStr);
            //取出前面两个数，取不到就拿-1代替
            int lastTwo = result.size() >= 2 ? result.get(result.size() - 2) : -1;
            int lastOne = result.size() >= 2 ? result.get(result.size() - 1) : -1;
            result.add(nextNum);
            if ((lastOne == -1 || lastTwo == -1 || lastTwo + lastOne == nextNum) && dfs(S, i, result)) {
                //为-1时，表示不足2个数，继续深一层探索；前两个数之和等于下一个数，符合，继续深一层探索；按当前状态深度搜索到底是成功的，返回true代表成功
                return true;
            }
            //前两个数之和不等于下一个数，这条路径不行，弹出当前加进去的数，在同一层延长一位继续搜索
            result.remove(result.size() - 1);
        }
        //false代表这条路行不通
        return false;
    }
}
